iT邦幫忙

2023 iThome 鐵人賽

DAY 4
0
SideProject30

UVA題型研究系列 第 4

DAY4:Function operations

  • 分享至 

  • xImage
  •  

04 UVA100 The 3n + 1 problem
內容
考慮以下的演算法:

  1.     輸入 n
    
  2.     印出 n
    
  3.     如果 n = 1 結束
    
  4.     如果 n 是奇數 那麼 n=3*n+1
    
  5.     否則 n=n/2
    
  6.     GOTO 2
    

例如輸入 22, 得到的數列: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

據推測此演算法對任何整數而言會終止 (當列印出 1 的時候)。雖然此演算法很簡單,但以上的推測是否真實卻無法知道。然而對所有的n ( 0 < n < 1,000,000 )來說,以上的推測已經被驗證是正確的。

給一個輸入 n ,透過以上的演算法我們可以得到一個數列(1作為結尾)。此數列的長度稱為n的cycle-length。上面提到的例子, 22 的 cycle length為 16.

問題來了:對任2個整數i,j我們想要知道介於i,j(包含i,j)之間的數所產生的數列中最大的 cycle length 是多少。
輸入說明
輸入可能包含了好幾列測試資料,每一列有一對整數資料 i,j 。 0< i,j < 1,000,000
輸出說明
對每一對輸入 i , j 你應該要輸出 i, j 和介於 i, j 之間的數所產生的數列中最大的 cycle length。
範例輸入 #1
1 10
10 1
100 200
201 210
900 1000
範例輸出 #1
1 10 20
10 1 20
100 200 125
201 210 89
900 1000 174

題目大意:在這個問題中,您將分析一個算法的屬性,該算法的分類對於所有可能的輸入都是未知的。

解題:如果 n 是奇數那麼 n=3*n+1,否則 n=n/2,當n = 1 時結束

#定義一個函數 a(n),用於計算從 n 開始的數列的步數
def a(n): 
    step = 1  # 初始化步數為 1
    
    #使用 while 迴圈,當 n 不等於 1 時,持續計算步數
    while n != 1:
        step += 1  # 增加步數
        #如果 n 是奇數,則將 n 更新為 3n+1;如果 n 是偶數,則將 n 更新為 n//2
        n = 3 * n + 1 if n % 2 else n // 2

return step  # 返回計算的步數

#進入一個無限循環,等待用戶輸入
while True:
    try:
        # 讀取一行輸入,並將其拆分成整數列表,存儲在 ip 中
        ip = list(map(int, input().split()))
    
        #找到 ip 列表中的最大值 m 和最小值 M
        m = max(ip)
        M = min(ip)
    
        #輸出 ip 列表的第一個和第二個元素,以及調用 a 函數計算的範圍從 M 到 m 的數列中最大步數
        print(ip[0], ip[1], max(map(a, range(M, m + 1))))

    except:
        #如果在 try 塊中發生異常,則退出循環,結束程式執行
        break

上一篇
DAY3:Carry after addition
下一篇
DAY5:Judgment of multiples
系列文
UVA題型研究30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言